﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.SortAlgorithm
{
    public static class Recursive_Activity_Selector
    {
        /// <summary>
        /// 递归
        /// </summary>
        /// <param name="works"></param>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        public static Work[] Recursive_Activity_Selector1(Work[] works, int start, int end)
        {
            List<Work> result = new List<Work>();
            var newWork = works.ToList().OrderBy((w) => { return w.End; }).ToArray();//首先按结束时间的升序排序

            var s = newWork[start];

            var m = start + 1;

            while(m<=end && newWork[m].Start <s.End)
            {
                m++;
            }

            if (m <= end)
            {
                result.Add(s);
                result.AddRange(Recursive_Activity_Selector1(newWork, m, end));
            }
            return result.ToArray();
        }

        /// <summary>
        /// 迭代
        /// </summary>
        /// <param name="works"></param>
        /// <returns></returns>
        public static Work[] Greedy_Activity_Selector(Work[] works)
        {
            var newWork = works.ToList().OrderBy((w) => { return w.End; }).ToArray();//首先按结束时间的升序排序
            var len = works.Length;

            List<Work> result = new List<Work>();

            result.Add(newWork[0]);
            var i =1;
            for (int m = 1; m <= len; m++)
            {
                if (newWork[m].Start >= newWork[i].End)
                {
                    result.Add(newWork[m]);
                    i = m;
                }
            }

            return result.ToArray();
        }
    }



    public class Work
    {
        public double Start
        {
            get;
            set;
        }
        public double End
        {
            get;
            set;
        }
    }
}
